package com.dh.leetcode.six;

import org.junit.Assert;
import org.junit.Test;

/**
 * @ClassName: _643_maximum_average_subarray_i
 * @Description: 643. 子数组最大平均数I
 * 给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
 * 示例：
 * 输入：[1,12,-5,-6,50,3], k = 4
 * 输出：12.75
 * 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
 * <p>
 * 提示：
 * <p>
 * 1 <= k <= n <= 30,000。
 * 所给数据范围 [-10,000，10,000]。
 * <p>
 * https://leetcode-cn.com/problems/maximum-average-subarray-i/
 * @Author: shouzimu
 * @Date: 2021/2/4 9:12
 */
public class _643_maximum_average_subarray_i {

    /**
     * 第一次提交使用了double，4ms
     * 后面看题解解释用int计算比double快，最后返回在转double，果然耗时2ms
     * @param nums
     * @param k
     * @return
     */
    public double findMaxAverage(int[] nums, int k) {
        int max = 0;
        for (int i = 0; i < k; i++) {
            max += nums[i];
        }
        int sum = max;
        for (int i = k; i < nums.length; i++) {
            sum -= nums[i - k];
            sum += nums[i];
            max = Math.max(sum, max);
        }
        return (Double.valueOf(max)) / k;
    }

    @Test
    public void findMaxAverageTest() {
        Assert.assertEquals(1d, findMaxAverage(new int[]{1}, 1), 5);
        Assert.assertEquals(12.75d, findMaxAverage(new int[]{1, 12, -5, -6, 50, 3}, 4), 5);
    }
}
